package com.ljy.my_study.lintcode.最长不重复字符串;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

/** 
* @author James
* @date 2018年4月12日 
*/
public class LongestNotRepeatingStrMain {
	public static String longestNotRepeatingStr(String str) {
		if(str==null||str.length()==0) {
			return str;
		}
		Map<Character,Integer> map=new HashMap<>();
 		char[] array=str.toCharArray();
		String result=str.substring(0,1);
		int startIndex=0;
		for(int i=0;i<array.length;i++) {
			char c=array[i];
			if(map.get(c)!=null) {
				if(i>startIndex) {
					String s=str.substring(startIndex,i);
					startIndex=map.get(c)+1;
					if(s.length()>result.length()) {
						result=s;
					}
					Iterator<Entry<Character,Integer>> it=map.entrySet().iterator();
					while(it.hasNext()) {
						Entry<Character,Integer> e=it.next();
						if(e.getValue()<startIndex) {
							it.remove();
						}
					}
					map.put(array[i], i);
					continue;
				}
			}
			map.put(array[i], i);
			if(i==array.length-1&&map.get(c)!=null) {
				String s=str.substring(startIndex,i+1);
				startIndex=map.get(c)+1;
				if(s.length()>result.length()) {
					result=s;
				}
			}
		}
		
		return result;
	}
	
	public static String longestNotRepeatingStr2(String str) {
		return null;
	}
	
	public static int lengthOfLongestSubstring(String str) {
        if(str==null||str.length()==0) {
			return 0;
		}
		Map<Character,Integer> map=new HashMap<>();
 		char[] array=str.toCharArray();
		String result=str.substring(0,1);
		int startIndex=0;
		for(int i=0;i<array.length;i++) {
			char c=array[i];
			if(map.get(c)!=null) {
				if(i>startIndex) {
					String s=str.substring(startIndex,i);
					startIndex=map.get(c)+1;
					if(s.length()>result.length()) {
						result=s;
					}
					Iterator<Entry<Character,Integer>> it=map.entrySet().iterator();
					while(it.hasNext()) {
						Entry<Character,Integer> e=it.next();
						if(e.getValue()<startIndex) {
							it.remove();
						}
					}
					map.put(array[i], i);
					continue;
				}
			}
			map.put(array[i], i);
			if(i==array.length-1&&map.get(c)!=null) {
				String s=str.substring(startIndex,i+1);
				startIndex=map.get(c)+1;
				if(s.length()>result.length()) {
					result=s;
				}
			}
		}
		
		return result.length();
    }
	
	
	public static void main(String[] args) {
//		System.out.println("result:"+longestNotRepeatingStr("an++--viaj"));
//		System.out.println("-----------------------");
//		System.out.println("result:"+longestNotRepeatingStr("aab1"));
//		System.out.println("-----------------------");
//		System.out.println("result:"+longestNotRepeatingStr("1234567123"));
//		System.out.println("-----------------------");
//		System.out.println("result:"+longestNotRepeatingStr("132131"));
//		System.out.println("-----------------------");
//		System.out.println("result:"+lengthOfLongestSubstring("1234567123"));
//		System.out.println("-----------------------");
		System.out.println("result:"+lengthOfLongestSubstring("abcabcbb"));
		System.out.println("-----------------------");
		System.out.println("result:"+longestNotRepeatingStr("abcabcbb"));
		System.out.println("-----------------------");
	}
}
